package _01_sort.leetcodeexerc;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author: mornd
 * @dateTime: 2023/6/23 - 14:58
 * 相对排序
 * 根据另一个数组的次序排序，将a1按照a2的顺序排序，多出的部分再由小到大排序
 */
public class Test1 {

    @Test
    public void test() {
        int[] a1 = {2, 5, 7, 9, 2, 5, 1, 6};
        int[] a2 = {5, 2, 1, 9};
        sort(a1, a2);
        System.out.println(Arrays.toString(a1));
    }

    // 计数排序
    public void sort(int[] a1, int[] a2) {
        int max = a1[0];
        int min = a1[0];
        for (int i = 1; i < a1.length; i++) {
            max = Math.max(a1[i], max);
            min = Math.min(a1[i], min);
        }
        int[] newArr = new int[max + 1];
        for (int j : a1) {
            newArr[j]++;
        }
        int index = 0;
        for (int i : a2) {
            while (newArr[i] > 0) {
                a1[index++] = i;
                newArr[i]--;
            }
        }
        // 将剩余元素取出
        for (int i = 0; i < newArr.length; i++) {
            if(newArr[i] > 0) {
                while (newArr[i] > 0) {
                    a1[index++] = i;
                    newArr[i]--;
                }
            }
        }
    }
}
